1. Field of the Invention
The present invention relates to a packet forwarding apparatus wherein a plurality of networks are connected to one another and packets are forwarded between the networks.
2. Description of the Related Art
Traffics (packets), which flow over an Internet, are increasing rapidly with an increase in Internet users. Since the same line can be shared between packets sent from a large number of users in a packet type communication system employed in the Internet, the cost per bandwidth can be less reduced. The non-execution of strict management of quality control or the like for each users also leads to the implementation of a cost reduction.
Owing to the advantage of the low cost, which is held by the packet type communication system, moves have been made to integrate telephone networks and enterprise networks which have heretofore been implemented by dedicated networks, into one by the Internet thereby to implement a reduction in communication cost. It is necessary to implement quality of service (QoS) such as a low delay time, a low discard rate, etc. which have been carried out by the conventional telephone networks or enterprise networks, and security even over the Internet for the purpose of integrating these plural networks into one.
As to QoS control for implementing QoS, forwarding or transfer control must be effected on respective packets with priority corresponding to a contract while specific applications (such as telephone traffics, etc.) and individual users (enterprises, etc.) taken as objects to be controlled are being identified. The QoS control is generally used in an ATM (Asynchronous Transfer Mode) switch. The QoS control of the ATM switch is implemented by a bandwidth monitoring device for monitoring the presence or absence of a breach of a contracted bandwidth at the entrance of a network, and a priority control forwarding device for preferentially forwarding each packet made compliant with the contracted bandwidth with the contracted priority.
The priority control forwarding device employed in the ATM switch has been described in, for example, Japanese Patent Application Laid-Open No. Hei 6-197128 (prior art 1). In the prior art 1, two output buffers for CBR (Constant Bit Rate) and VBR (Variable Bit Rate) are provided every output lines, and the priority for outputting each cell stored in the buffer for CBR is set higher than that for each cell stored in the buffer for VBR, whereby a communication delay time in the ATM switch is limited to within a constant value with respect to a cell group of CBR traffics having a strict restriction on a communication delay.
Further, the bandwidth monitoring function employed in the ATM switch has been described in, for example, Chapter 4 of xe2x80x9cThe ATM Forum Traffic Management Specification Version 4.0xe2x80x9d (prior art 2). In the prior art 2, bandwidth monitoring based on GCRA (Generic Cell Rate Algorithm) corresponding to an algorithm for bandwidth monitoring is effected at the entrance of each network, whereby resources for the network can be prevented from being occupied by a specific user.
The ATM switch is a connecting device for connection type communications, wherein a user packet having a fixed length is communicated after a connection has been established between terminals. When the ATM switch receives a cell from an input line, it reads bandwidth monitoring information and QoS control information such as priority information for cell transfer, etc. from a connection information table provided in the ATM switch, based on connection information indicative of users and applications, included in a header of the input cell, thereby to perform bandwidth monitoring based on the bandwidth monitoring information and priority control of cell forwarding according to the priority information.
On the other hand, a router device is a connecting device for packet type (connection-less type) communications, in which a user packet is communicated without establishing a connection between terminals in advance. The router does not have the connection information table for storing the bandwidth monitoring information and the QoS control information as in the ATM switch. Therefore, the router device must be provided with a flow detector or detection device for detecting bandwidth monitoring information and priority information from header information set every input packets in order to perform priority transfer control and bandwidth monitoring. It is further necessary to control the bandwidth monitoring and the priority transfer, based on the bandwidth monitoring information and the priority information detected by the flow detector.
In the specification of the present application, a packet identification condition defined by a combination of a plurality of items of parameter information included in a packet header will be called xe2x80x9cflow conditionxe2x80x9d, a traffic comprised of a series of packets coincident with the flow condition will be called xe2x80x9cflowxe2x80x9d, and determination as to whether header information of each received packet coincides with a predetermined flow condition, will be called xe2x80x9cflow detectionxe2x80x9d, respectively.
The QoS control employed in the router device has been disclosed in, for example, Japanese Patent Application Laid-Open No. Hei 6-232904 (prior art 3). In order to execute the QoS control, a router disclosed in the prior art 3 has a mapping table which holds priorities in association with all the combinations of priority identification information and protocol (upper application) information which will be included within the packet header so that the router executes priority forwarding control by determining the priority for each input packet from the mapping table.
As another prior art related to the QoS control employed in the router device, there is known Diffserv (Differentiated Service) indicated by RFC2475 (prior art 4) of IETF (Internet Engineering Task Force).
According to the prior art 4, for example, when an edge router 326 or 327 called a boundary node located in the entrance of an Internet 325 in a network shown in FIG. 2 in which QoS is contracted between enterprise networks A, B, C and D and the Internet 325, receives a packet sent from an enterprise network 321 or 324, it performs a flow detection through a flow detector called classifier, with a source IP address and a destination IP address, a source port number and a destination port number, protocol, etc. in a TCP/IP header as flow conditions respectively. Each boundary node monitors a bandwidth for each flow detected by the classifier and writes the result of determination of DS indicative of each priority in the Internet 325 into a DS field (TOS field) of each received packet. A backbone router (called an interior node in the prior art 4) corresponding to a core node of the Internet 325 performs QoS control on each packet, based on the value of each DS field referred to above.
The flow detection is a technique necessary even for filtering to keep security. In a connection type communication network, for example, each terminal is controlled so that a connection is established only between the terminal and a pre-allowed communication opposite party, and a connection between the terminal and a non-allowed communication opposite party is prohibited from establishing, whereby the reception of cells from an unexpected terminal can be avoided. However, since there is a possibility that in a packet type communication network which starts communication without establishing a connection, each individual terminals will receive packets from all the other terminals connected to networks, it is necessary to provide a filtering function for completely discarding packets sent from unexpected opposite parties.
In order to perform filtering on each received packet, a router needs to effect a flow detection for identifying each packet for filtering, on each input packet in a manner similar to the QoS control to thereby generate control information indicative of whether or not packet transfer is allowed and to selectively transfer or discard the input packets.
The filtering employed in the router device has been described in, for example, Japanese Patent Application Laid-Open No. Hei 6-104900 (prior art 5). In the prior art 5, a LAN-to-LAN connecting device is provided with a filtering table indicative of the correspondence between source addresses and destination addresses, and only such packets that are proceeding from the source address to the destination address registered in the filtering table is set as an object to be transferred, whereby the filtering is implemented.
When the number of flows to be detected by each router increases as Internet users increase, flow detection devices capable of setting a large number of flow conditions are necessary for the respective routers. With an increase in traffic flowing over the Internet and the speeding up of a line rate, the shortening of a processing desired time interval per packet and high speed execution of QoS control (priority forwarding control, bandwidth monitoring, etc.) and filtering under high volumes of flow condition entries are required for each router. It is also desirable that a manager for each router is able to easily set a variety of flow conditions to an entry table of each router. However, these problems remain unsolved in the prior arts 3, 4 and 5.
A principal object of the present invention is to provide a packet forwarding apparatus capable of setting flow conditions comprised of a plurality of items including user identification information, protocol information, priority identification information, etc. in large quantity and performing a flow detection, QoS control and filtering at high speed.
Another object of the present invention is to provide a packet forwarding apparatus capable of flexibly coping with the request of a router""s manager and easily registering a variety of flow conditions.
In a network wherein routers are connected to one another by an ATM network or frame relay network as shown in FIG. 46 by way of example, there is a possibility that a congestion incident to an excessive traffic will occur in a public ATM network 4301 and hence QoS cannot be maintained. Therefore, high-speed QoS control is necessary even for the ATM network and frame relay network which connect between the routers. However, the prior arts 3, 4 and 5 lack a useful technical disclosure related to a method of determining connections such as VC/VP (Virtual Channel/Virtual Path), DLCI, etc. for high-speed flow detection and QoS control necessary for these networks.
A further object of the present invention is to provide a router which rapidly determines VC/VP or DLCI and is effective for QoS control of an ATM network and a frame relay network.
In order to achieve the above objects, there is provided a packet forwarding apparatus according to the present invention, wherein an entry table referred to for detecting flows to which respective input packets belong, is divided into a plurality of subtables respectively corresponding to the values of flow attributes associated with the respective packets.
Described more specifically, according to the present invention, the packet forwarding apparatus provided with a plurality of line interface units each connected to an input line and an output line, comprises: a routing processing unit for referring to a routing table, based on header information of packets received from the input lines by said line interface units to specify one of the output lines for each of said received packets to output the packet; a flow detection unit for retrieving, by referring to an entry table with a plurality of entries each including a flow condition and control information therein, control information defined by one of said entries with a flow condition coincide with that of the header information of said received packet; and a packet forwarding unit for transferring the received packet to one of said line interface units connected to the output line specified by the routing processing unit; and wherein said entry table comprises of a plurality of subtables respectively corresponding to the values of flow attributes associated with the received packets, and the flow detection unit retrieves the control information for each of said received packets from the subtable specified by the value of the flow attribute associated with the received packet, and the packet forwarding unit controls the transfer of each of said received packets to one of said line interface units in accordance with the control information notified from the flow detection unit.
According to a preferred embodiment of the present invention, the entry table comprises a first table for storing the plurality of entries therein and a list table for storing therein pointer addresses for accessing the entries lying within the first table. The list table is divided into a plurality of sub-list tables corresponding to the values of the flow attributes. The flow detection unit refers to one of said sub-list tables specified by the value of the flow attribute corresponding to each received packet and retrieves the entry with a flow condition coincident with that of the header information of the received packet, based on a pointer address stored in the sub-list table.
The flow attribute is, for example, a line number indicative of an input line of the received packet or a line number indicative of an output line to output the received packet.
The flow attribute may be a MAC identifier produced from a source MAC address included in the header information of each received packet, a MAC identifier produced from a destination MAC address included in the header information of the received packet, a source subnet identifier for identifying a subnet to which a source IP address included in the header information of the received packet belongs, or a destination subnet identifier for identifying a subnet to which a destination IP address included in the header information of the received packet belongs. Each entry registered in the entry table includes, as the flow condition, at least one type of information selected from among a line number indicative of an input line of the received packet, a line number indicative of an output line of the received packet, and address information, application identification information and identification information on service priority included in the header of the received packet, for example.
In the packet forwarding apparatus according to the present invention, for example, each entry registered in the entry table includes, as the control information, at least one of priority information indicative of priority for the transmission of the received packet to the output line and forwarding control information indicative of whether the transfer of the packet to other output lines is required. The packet forwarding unit performs at least one of filtering control of the received packet and priority control for the transfer of the packet to the corresponding output line in accordance with the control information notified from the flow detection unit.
One feature of the present invention resides in that each entry registered in the entry table includes, as the control information, priority information indicative of priority for the transmission of the received packet to one of the output lines, and TOS (Type of Service) information, and the packet forwarding unit rewrites TOS information included in header information of the received packet in accordance with the TOS information notified from the flow detection unit as the control information and thereafter performs priority control for the transfer of the received packet to the output line in accordance with the priority information notified from the flow detection unit as the control information.
Another feature of the present invention resides in that each entry registered in the entry table includes priority information and connection identification information as the control information, the packet forwarding unit adds the connection identification information notified form the flow detection unit as the control information to the received packet and thereafter performs priority control for the transfer of the received packet to the output line in accordance with the priority information notified from the flow detection unit as the control information, and each line interface unit outputs the packet received from the packet forwarding unit to a connection corresponding to the connection identification information formed over the corresponding output line.
A further feature of the present invention resides in that the list table comprises a first list table for use in filtering control and a second list table for use in forwarding control, and the first and second list tables are divided into a plurality of subtabls corresponding to the values of the flow attributes respectively, and the flow detection unit selectively refers to the first and second list tables for each received packet to thereby retrieve control information for filtering control and control information for forwarding control, both of which are related to the received packet.
Other problems to be solved by the present application, and their solving device will become apparent from the section of embodiments according to the present invention and the accompanying drawings.